package wwl.lsf;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @Title
 * @Author wangwenliang
 * @Date 2021/7/22
 * @Description
 */
public class 复原IP地址 {

    public static void main(String[] args) {

        String s = "25525511135";
//        String s = "2";
//        String substring = s.substring(0, 2);
//        System.out.println("substring = " + substring);
        Solution2 solution = new Solution2();
        List<String> strings = solution.restoreIpAddresses(s);
        System.out.println("strings = " + strings);
        SolutionSelf solutionSelf = new SolutionSelf();
        List<String> ip = solutionSelf.getIP(s);
        System.out.println("ip = " + ip);
    }

}

class Solution {
    public List<String> restoreIpAddresses(String s) {
        int len = s.length();
        List<String> res = new ArrayList<>();
        // 如果长度不够，不搜索
        if (len < 4 || len > 12) {
            return res;
        }

        Deque<String> path = new ArrayDeque<>(4);
        int splitTimes = 0;
        dfs(s, len, splitTimes, 0, path, res);
        return res;
    }

    /**
     * 判断 s 的子区间 [left, right] 是否能够成为一个 ip 段
     * 判断的同时顺便把类型转了
     *
     * @param s
     * @param left
     * @param right
     * @return
     */
    private int judgeIfIpSegment(String s, int left, int right) {
        int len = right - left + 1;

        // 大于 1 位的时候，不能以 0 开头
        if (len > 1 && s.charAt(left) == '0') {
            return -1;
        }

        // 转成 int 类型
        int res = 0;
        for (int i = left; i <= right; i++) {
            res = res * 10 + s.charAt(i) - '0';
        }

        if (res > 255) {
            return -1;
        }
        return res;
    }

    /**
     * splitTimes：已经分割出多少个 ip 段；
     * begin：截取 ip 段的起始位置；
     * path：记录从根结点到叶子结点的一个路径（回溯算法常规变量，是一个栈）；
     * res：记录结果集的变量，常规变量。
     */
    private void dfs(String s, int len, int split, int begin, Deque<String> path, List<String> res) {
        if (begin == len) {
            if (split == 4) {
                res.add(String.join(".", path));
            }
            return;
        }

        // 看到剩下的不够了，就退出（剪枝），len - begin 表示剩余的还未分割的字符串的位数
        if (len - begin < (4 - split) || len - begin > 3 * (4 - split)) {
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (begin + i >= len) {
                break;
            }

            int ipSegment = judgeIfIpSegment(s, begin, begin + i);
            if (ipSegment != -1) {
                // 在判断是 ip 段的情况下，才去做截取
                path.addLast(ipSegment + "");
                dfs(s, len, split + 1, begin + i + 1, path, res);
                path.removeLast();
            }
        }
    }


}

class Solution2 {

    public List<String> restoreIpAddresses(String s) {
        int len = s.length();
        List<String> res = new ArrayList<>();
        if (len > 12 || len < 4) {
            return res;
        }

        Deque<String> path = new ArrayDeque<>(4);
        dfs(s, len, 0, 4, path, res);
        return res;
    }

    // 需要一个变量记录剩余多少段还没被分割

    private void dfs(String s, int len, int begin, int residue, Deque<String> path, List<String> res) {
        if (begin == len) {
            if (residue == 0) {
                res.add(String.join(".", path));
            }
            return;
        }

        for (int i = begin; i < begin + 3; i++) {
            if (i >= len) {
                break;
            }
//                感觉(residue * 3 < len - i)替换为((residue-1) * 3 < len - i - 1)更好理解。
            if (residue * 3 < len - i) {
                continue;
            }

            if (judgeIpSegment(s, begin, i)) {
                String currentIpSegment = s.substring(begin, i + 1);
                path.addLast(currentIpSegment);

                dfs(s, len, i + 1, residue - 1, path, res);
                path.removeLast();
            }
        }
    }

    private boolean judgeIpSegment(String s, int left, int right) {
        int len = right - left + 1;
        if (len > 1 && s.charAt(left) == '0') {
            return false;
        }

        int res = 0;
        while (left <= right) {
            res = res * 10 + s.charAt(left) - '0';
            left++;
        }

        return res >= 0 && res <= 255;
    }


}

class SolutionSelf {

    public List<String> getIP(String ipStr) {

        List<String> res = new ArrayList<>();
        int length = ipStr.length();
        if (length < 4 || length > 12) {
            return res;
        }

        Deque deque = new ArrayDeque<>();

        dgui(ipStr, ipStr.length(), 0, 4, deque, res);

        return res;
    }

    public void dgui(String str, int length, int begin, int remaining, Deque temp, List<String> res) {

        if (begin >= length) {
            if (remaining == 0) {
                res.add(String.join(".", temp));
            }
            return;
        }

        for (int i = begin; i < begin + 3; i++) {
            if (i >= length) {
                break;
            }
            //剩下的字符都是3个也还有剩余,这种的是不满足需求的跳过
            if (length - i > remaining * 3) {
                continue;
            }
            if (checkJumpIP(str, begin, i + 1)) {
                temp.addLast(str.substring(begin, i + 1));
                dgui(str, length, i + 1, remaining - 1, temp, res);
                temp.removeLast();
            }


        }


    }

    public boolean checkJumpIP(String str, int left, int right) {

        if (right - left > 1) {
            if (str.substring(left, left + 1).equals("0")) {
                return false;
            }
        }
        int i = Integer.valueOf(str.substring(left, right)).intValue();

        return i >= 0 && i <= 255;
    }


}
